The problem can be found at the following link: Question Link
I solved this problem using dynamic programming. Here's the intution behind it:
- To calculate the number of unique subsequences for the 'ith' character, it's simply double the number of subsequences for the 'i-1th' character.
- However, there's a catch. We need unique subsequences, so we check the last occurrence of the current character and subtract it from the total number of subsequences to get our final answer.
let s = "ngfg"
- { "" } = 1
- { "", "n" } = 2 , for i = 0
- { "", "n" , "g", "ng" } = 4 , for i = 1
- { "", "n" , "g", "f", "ng", "gf", "nf", "ngf" } = 8 , for i = 2
- { "", "n" , "g", "f", "ng", "gf", "gg", "nf", "gg", "ngf", "ngg", "nfg", "gfg", "ngfg" } = 14 , for i = 3
In the last step, since the last occurrence of 'g' is at index 1, we have already included subsequences like {"g", "ng"}. So, our final answer is 16 - 2 = 14.
Here's how it works:
- Create a vector
last
of size 26, initialized with -1. This vector will store the last occurrence of each character in the strings
. - Create a dynamic programming array
dp
of sizen+1
, wheren
is the length of the input strings
. Initializedp[0]
to 1 because there is one empty subsequence. - Loop through the characters of the string
s
from left to right (indexi
from 1 ton
).- Calculate
dp[i]
asdp[i-1]*2
, which represents the total number of subsequences that include the current characters[i-1]
. - Find the last occurrence of the current character
s[i-1]
using thelast
vector. - If
lastOccur
is not -1 (i.e., the character has occurred before), subtractdp[lastOccur]
fromdp[i]
. This step removes the count of subsequences that include duplicate characters, ensuring distinct subsequences. - Perform modulo
mod
to keep the values ofdp[i]
within a valid range. - Update the
last
vector with the current indexi-1
for the characters[i-1]
.
- Calculate
- Return
dp[n]
, which represents the total number of distinct subsequences of the input strings
."
- Time Complexity: The algorithm runs in
O(n)
time, where n is the length of the input strings
. - Auxiliary Space Complexity: The algorithm uses
O(26)
extra space for thelast
vector andO(n)
space for thedp
array, resulting in a total auxiliary space complexity ofO(n)
.
class Solution {
public:
int mod = 1e9 + 7;
int distinctSubsequences(string s) {
int n = s.size();
vector<int> last(26, -1);
long long dp[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] * 2;
int lastOccur = last[s[i - 1] - 'a'];
if (lastOccur != -1) {
dp[i] -= dp[lastOccur];
if (dp[i] < 0)
dp[i] += mod;
}
dp[i] %= mod;
last[s[i - 1] - 'a'] = i - 1;
}
return dp[n];
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.